package algorthm.systemTraning.linkedList;

/**
 * @className: UseTwoStackAsQueue
 * @Description:  现在有一颗树，使用广度有限遍历来遍历它，但是不能使用队列的数据结构。
 * 此题目是让我们使用两个栈代替队列的。
 * @Author: wangyifei
 * @Date: 2022/9/12 22:47
 */
public class UseTwoStackAsQueue {
    public static void main(String[] args) {
        Queue q = new Queue();
        for (int i = 0; i < 10; i++) {
            q.queueEnter(i);
        }

        for (int i = 0; i < 10; i++) {
            System.out.println(q.queueExit());
        }
    }
    public static class Queue{
        // A B C 然后按照放入的顺序放入到 stack2 C B A
        // 所有要保证 stack2 一定要出完栈才能从 stack1 中拿数据，
        // 从 stack1 中拿数据一定要拿完
        Stack stack1 = new Stack();
        Stack stack2 = new Stack();
        public void queueEnter(int i){
            stack1.push(i);
        }
        public int queueExit(){
            int ans = 0 ;
            // 保证 stack1 有数据并且 stack2 中的数据是 0 的时候，再将 stack1 中的数据放入到 stack2 中
            // 这样入栈的顺序就不会被打乱了。
            if(stack1.size > 0 && stack2.size() == 0){
                // 还需要一下子就移动过去才行。
                while(stack1.size > 0){
                    stack2.push(stack1.pop());
                }
            }
            ans = stack2.pop();
            return ans ;
        }
    }

    public static class Stack {
        private int[] tabs ;
        private static final int DEFAULT_CAPACITY = 20 ;
        private int capacity ;
        private int size ;
        private int head ;

        public int capacity() {
            return capacity;
        }

        public int size() {
            return size;
        }

        public Stack(){
            tabs = new int[DEFAULT_CAPACITY];
            capacity = DEFAULT_CAPACITY ;
        }
        public Stack(int capacity){
           tabs = new int[capacity];
           this.capacity = capacity ;
        }
        {
            size = 0 ;
            head = 0 ;
        }
        public void push(int i){
            if(capacity >= size){
                tabs[head++] = i ;
                size++;
            }else {
                throw new IndexOutOfBoundsException();
            }
        }
        public int pop(){
            int ans = 0;
            if(size == 0){
                throw new IndexOutOfBoundsException();
            }else{
                ans = tabs[head - 1];
                head--;
                size--;
            }
            return ans ;
        }
    }
}
